package string.inter;

public interface CustString {

    /**
     * 复制串
     *
     * @return
     */
    CustString strCopy();

    /**
     * 清空串
     */
    void clearString();

    /**
     * 串是否为空
     *
     * @return
     */
    boolean stringEmpty();

    /**
     * 比较串
     *
     * @param string 要比较的串
     * @return
     */
    int strCompare(CustString string);

    /**
     * 串连接
     *
     * @param s1 要连接的第一个串
     * @param s2 要连接的第二个串
     * @return 返回连接后的串
     */
    CustString concat(CustString s1, CustString s2);

    /**
     * 从pos位置开始匹配子串，返回字串开始的下标
     *
     * @param s   要匹配的字符串
     * @param pos 从第pos的位开始匹配
     * @return 返回匹配到的子串的第一个字母的下标
     */
    int index(CustString s, int pos);

    /**
     * 用target串替换source串
     *
     * @param source 要被替换的串
     * @param target 要被换入原串的字符串
     * @return
     */
    CustString replace(CustString source, CustString target);

    /**
     * 将串s插入pos位置
     *
     * @param s   要插入的串
     * @param pos 要插入的位置
     * @return
     */
    void strInsert(CustString s, int pos);

    /**
     * 从pos位置开始删除len个字符
     *
     * @param pos
     * @param len
     * @return
     */
    CustString strDelete(int pos, int len);

    /**
     * 串赋值
     *
     * @param chs
     */
    void assign(char[] chs);

    /**
     * 获取第i个字符
     *
     * @param i
     * @return
     */
    char charAt(int i);

    /**
     * 获取字符串长度
     *
     * @return
     */
    int strLength();

    /**
     * 字符串反转
     */
    void strReverse();

    /**
     * 输出字符串
     */
    void printStr();

    default int[] getNext() {
        int k = -1;
        int[] next = new int[this.strLength()];
        next[0] = k;
        for (int i = 1; i < this.strLength(); i++) {
            while (k > -1
                    && this.charAt(i) != this.charAt(k + 1)) {
                k = next[k];
            }
            if (this.charAt(i) == this.charAt(k + 1)) {
                k++;
            }
            next[i] = k;
        }
        return next;
    }

    /**
     * KMP字符串匹配算法(从头匹配)
     *
     * @param target 要匹配的字符串
     * @return 返回匹配到的字符串的第一个字符的下标
     */
    default int kmp(CustString target) {
        return kmp(0, target);
    }

    /**
     * KMP字符串匹配算法（从pos位开始匹配）
     *
     * @param pos    从pos位开始匹配
     * @param target 要匹配的字符串
     * @return 返回匹配到的字符串的第一个字符的下标
     */
    default int kmp(int pos, CustString target) {
        int[] next = getNext();
        int p = -1;
        if (target.strLength() > this.strLength()) {
            return -1;
        }

        for (int i = pos; i < this.strLength(); i++) {
            while (p > -1
                    && this.charAt(i) != target.charAt(p + 1)) {
                p = next[p];
            }
            if (this.charAt(i) == target.charAt(p + 1)) {
                p++;
            }
            if (p == target.strLength() - 1) { // 结果减去目标串长度，得到匹配到的串的首字母下标
                return i - (target.strLength() - 1);
            }
        }
        return -1;
    }

}
